La grammatica dell'appartenenza
A differenza delle coppie ordinate $(a, b)$ o degli $n$-tuple, dove la posizione è fondamentale, un insieme $\{a, b\}$ è definito esclusivamente dai suoi elementi. Pertanto, $\{a, b\} = \{b, a\}$. Questa indifferenza all'ordine ci permette di concentrarci sulla identità dell'appartenenza.
Un'inclusione $A \subseteq B$ implica che ogni elemento di $A$ risieda in $B$. Tuttavia, un sottoinsieme proprio $A \subset B$ richiede di più: $B$ deve contenere almeno un elemento che sia non in $A$.
L' insieme delle parti $\mathcal{P}(S)$ è l'insieme di tutti i possibili sottoinsiemi di $S$. Se $|S| = n$, allora $|\mathcal{P}(S)| = 2^n$, che rappresenta la scala esponenziale delle possibilità fondamentali.
Il ponte logico: Meccanica degli insiemi
Le operazioni sugli insiemi sono le manifestazioni fisiche dei pensieri logici:
- Unione ($A \cup B$): Il logico OR. Gli elementi appartenenti a $A$ o a $B$.
- Intersezione ($A \cap B$): Il logico E. Gli elementi appartenenti sia a $A$ che a $B$.
- Insiemi disgiunti ($A \cap B = \emptyset$): Condizioni logiche mutuamente esclusive.
Esempio risolto: Il database degli studenti
Considera un database $D_1 = \{\text{Garth, Erin, Marty}\}$. Definiamo due predicati:
- Insieme $A$: Studenti alti più di 5'10" $\to \{\text{Garth, Marty}\}$.
- Insieme $B$: Studenti con nomi che terminano in 'y' $\to \{\text{Marty}\}$.
L' Intersezione $A \cap B$ dà come risultato $\{\text{Marty}\}$. Questo dimostra come il logico "E" filtri una popolazione in base a criteri sovrapposti. Marty è l'unico studente che soddisfa entrambe le condizioni: essere alto e avere un nome che termina in 'y'.
$x \in A \cap B \iff (x \in A) \land (x \in B)$